#define  _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <string>
#include <cassert>
using namespace std;


//#define a 10

//void foo();
//
//void Test1()
//{
//	printf("%d..", a);
//	foo();
//	printf("%d\n", a);
//}
//
//void foo(void) 
//{
//	#undef a
//	#define a 50
//}
//
//void Test2(void)
//{
//	printf("%d..", a);
//	foo();
//	printf("%d\n", a);
//}


//void Test3()
//{
//	printf("%d..", a);
//
//	#undef a
//	#define a 50
//
//	printf("%d..", a);
//}
//
//void Test4()
//{
//	printf("%d..", a);
//}

void Test5(void)
{
    int a[1000000] = { 0 };
    a[1] = 1, a[2] = 2;
    for (int i = 3; i < 1000000; ++i)
    {
        a[i] = ((a[i - 1] * 2) + a[i - 2]) % 32767;
    }

    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; ++i)
        {
            int k = 0;
            scanf("%d", &k);

            printf("%d\n", a[k]);
        }
    }
}

void Test6(void)
{
    string s;
    s.reserve(1000);

    getline(cin, s);

    int alcnt = 0, blcnt = 0, numcnt = 0, othcnt = 0;
    for (auto i : s)
    {
        if (isalpha(i))
            ++alcnt;
        else if (isblank(i))
            ++blcnt;
        else if (isdigit(i))
            ++numcnt;
        else
            ++othcnt;
    }
    cout << alcnt << endl;
    cout << blcnt << endl;
    cout << numcnt << endl;
    cout << othcnt << endl;
}

int* runningSum(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;

    int* ans = (int*)malloc(sizeof(int) * numsSize);
    assert(ans);

    int j = 0;
    ans[j++] = nums[0];
    for (int i = 1; i < numsSize; ++i)
    {
        ans[j++] = nums[i] + ans[j - 1];
    }

    return ans;
}

int searchInsert1(int* nums, int numsSize, int tar)
{
    int left = 0, right = numsSize - 1;

    while (left <= right)
    {
        int mid = (left + right) >> 1;

        if (nums[mid] > tar)
            right = --mid;
        else if (nums[mid] < tar)
            left = ++mid;
        else
            return mid;
    }

    return right + 1;
}

int searchInsert2(int* nums, int numsSize, int tar)
{
    if (tar < nums[0])
        return 0;
    if (tar > nums[numsSize - 1])
        return numsSize;

    int left = 0, right = numsSize - 1;

    while (left <= right)
    {
        int mid = (left + right) >> 1;

        if (nums[mid] > tar)
            right = --mid;
        else if (nums[mid] < tar)
            left = ++mid;
        else
            return mid;
    }

    return left;
}

int main()
{
	/*Test1();
	Test2();*/
	/*Test3();
	Test4();*/
    Test5();

	return 0;
}